package leetcode;

import java.util.ArrayList;
import java.util.List;

public class Code002 {

	
	/**
	 * Definition for singly-linked list.
	 * public class ListNode {
	 *     int val;
	 *     ListNode next;
	 *     ListNode(int x) { val = x; }
	 * }
	 * 链表存储的数是低位在前
	 * 
	 */
	class Solution {
	    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
	    	//链不止一个节点时
	    	List<Integer> cache = new ArrayList<>();
	    	
	    	//遍历链表求和
	    	for( ; (l1!= null && l1.next != null) || (l2!= null && l2.next != null);){
	    		int l1val = 0;
	    		int l2val = 0;
	    		if(l1 != null){
	    			l1val = l1.val;
	    			l1 = l1.next;
	    		}
	    		if(l2 != null){
	    			l2val = l2.val;
	    			l2 = l2.next;
	    		}
	    		cache.add(l1val+l2val);//将两数之和保存到List中
	    	}
	    	cache.add((l1 == null ? 0 :l1.val)+(l2 == null ? 0 :l2.val));//尾节点之和
	    	
	    	int len = cache.size();
	    	ListNode ret = null;
	    	
	    	ListNode retTemp = null;
	    	for(int i = 0 ; i < len ; i++){
	    		if(cache.get(i)/10 == 0 ){
	    			//无进位
	    			if(i== 0 ){
	    				retTemp = ret = new ListNode(cache.get(i));
	    			}else{
	    				retTemp.next = new ListNode(cache.get(i));
	    				retTemp = retTemp.next;
	    				
	    			}
	    		}else{
	    			//有进位
	    			if(i== 0 ){
	    				retTemp = ret = new ListNode(cache.get(i)%10);
	    			}else{
	    				retTemp.next = new ListNode(cache.get(i)%10);
		    			retTemp = retTemp.next;
	    			}
	    			if(i+1 < len){
	    				cache.set(i+1, cache.get(i+1)+1);
	    			}else{
	    				//链表之和节点数大于原链表节点数
	    				retTemp.next = new ListNode(1);
	    			}
	    			
	    		}
	    	}
	    	
			return ret;
	        
	    }
	}
}
class ListNode {
  int val;
  ListNode next;
  ListNode(int x) { val = x; }
 }
